package lcr;

public class Test0077 {
}

class Solution0077_1 {
    public ListNode sortList(ListNode head) {
        if (head==null) return null;
        return mergeSort(head,getRight(head));
    }

    public ListNode mergeSort(ListNode l,ListNode r){
        if(l==null||r==null) return l!=null?l:r;

        l=mergeSort(l, getRight(l));
        r=mergeSort(r,getRight(r));

        ListNode ans = new ListNode(),cur=ans;
        while (l!=null&&r!=null){
            cur.next=l.val<r.val?l:r;

            cur=cur.next;
            if (cur==l) l=l.next;
            else r=r.next;
        }

        cur.next=l!=null?l:r;

        return ans.next;
    }

    public ListNode getRight(ListNode node){
        ListNode l = node,r = node.next;

        while (r!=null&&r.next!=null){
            l=l.next;
            r=r.next.next;
        }

        ListNode ans = l.next;
        l.next=null;
        return ans;
    }
}
